package base;

/**
 * 并查集
 */
public class UnionFindSet {

    public void init(int[] s) {
        for (int i = 0; i < s.length; i++) {
            s[i] = i; // 初始化每个节点的祖宗节点为自己
            //也可以初始化为-1，祖宗节点的值用于记录每个集合的元素个数(用复数表示，区别祖宗节点的值),或者可以单独用一个rank[]数组记录集合数
            //s[i] = 1;
        }
    }
    public int find(int[] s, int x) {
        while (s[x] != x) // 循环找到x节点的祖宗节点
            x = s[x];
        return x;
    }

    public void union(int[] s, int x, int y) {
        // 先查询x,y的祖宗节点，判断x,y是否不在同一个集合
        int xRoot = find(s,x);
        int yRoot = find(s,y);
        if (xRoot == yRoot) return;

        s[xRoot] = yRoot; // x 集合合并到y集合，
        // 上面这里也可以根据两个集合的元素数量(rank[x])来判断哪个集合大，将较小的树合并到较大的树，保持树的相对平衡，提高效率
    }
}
